#include<iostream>
#include <stack>
using namespace std;

struct node 
{
	int data;
	node *link;
};

void create(node **phead,int *a, int len)
{
	if (*phead==NULL||a==NULL)
	{
		return;
	}
	else
	{
		node *pcur=*phead;
		for (int i=1;i<len;i++)
		{
			node *pnode=new node;
			pnode->data=a[i];
			pcur->link=pnode;
			pcur=pcur->link;
	
		 }
		pcur->link=NULL;//
	}
}

void printnodelist(node *phead)
{

  stack<node*> mystack;
  node *pcur=phead;
  while(pcur)
  {
	  mystack.push(pcur);
	  pcur=pcur->link;
  }
  while(!mystack.empty())
  {
	  pcur=mystack.top();
	  cout<<pcur->data<<" ";
	  mystack.pop();
  }
}

void printnodelist_recursion(node *phead)
{

	if (phead!=NULL)
	{
		node *pcur=new node;
		pcur=phead;
		if (pcur->link)
		{
			
			printnodelist_recursion(pcur->link);
			
		}
		cout<<pcur->data<<" ";
	}

}

void Reverselist( node *&head)
{
   node *p=head;
   node *pre=NULL;
   node *pnext=NULL;
  while (p)
  {
	  pnext=p->link;
	  if (pnext==NULL)
	  {
		  pre=head;
	  }
	  p->link=pre;
	  pre=p;
	  p=pnext;
  }
  head=pre;
}
void printlist(node *head)
{
	if (head==NULL)
	{
		return;
	}
	node *p=head;
	while(p)
	{
		cout<<p->data<<" ";
		p=p->link;
	}

}

node* mubble(node *pheadA, node *pheadB)
{
	if (pheadA==NULL)
	{
		return pheadB;
	}
	if (pheadB==NULL)
	{
		return pheadA;
	}
	node *c=NULL;
	if (pheadA->data>pheadB->data)
	{
		c=pheadB;
		pheadB=pheadB->link;
		c->link=NULL;
		
	}
	else
	{
		c=pheadA;
		pheadA=pheadA->link;
		c->link=NULL;
		
	}
	node *ptemp=c;
	while(pheadA!=NULL&&pheadB!=NULL)
	{
		if (pheadA->data<pheadB->data)
		{
			ptemp->link=pheadA;
			pheadA=pheadA->link;
			ptemp=ptemp->link;
			ptemp->link=NULL;
			
		}
		else /*if(pheadA->data>pheadB->data)*/
		{
			ptemp->link=pheadB;
			pheadB=pheadB->link;
			ptemp=ptemp->link;
			ptemp->link=NULL;
			
		}
	/*	else
		{
			ptemp=pheadA;
			pheadA=pheadA->link;
			ptemp->link=pheadB;
			ptemp=ptemp->link;
			ptemp->link=NULL;

		}*/

	}
	if (pheadA)
	{
		ptemp->link=pheadA;
	}
	if (pheadB)
	{
		ptemp->link=pheadB;
	}
	return c;
	
}



node* Merge(node* pHead1, node* pHead2)
{
	if(pHead1 == NULL)
		return pHead2;
	else if(pHead2 == NULL)
		return pHead1;

	node* pMergedHead = NULL;

	if(pHead1->data < pHead2->data)
	{
		pMergedHead = pHead1;
		pMergedHead->link = Merge(pHead1->link, pHead2);
	}
	else
	{
		pMergedHead = pHead2;
		pMergedHead->link = Merge(pHead1, pHead2->link);
	}

	return pMergedHead;
}


node *mergenode(node *head1, node *head2)
{
	if (head1==NULL)
	{
		return head2;
	}
	if (head2==NULL)
	{
		return head1;
	}
	node *head=NULL;
	node *p1=NULL;
	node *p2=NULL;
	if (head1->data<head2->data)
	{
		head=head1;
		p1=head1->link;
		p2=head2;
	}
	else
	{
		head=head2;
		p2=head2->link;
		p1=head1;
	}
	node *pcurrent=head;
	while(p1!=NULL&&p2!=NULL)
	{
		if (p1->data<=p2->data)
		{
			pcurrent->link=p1;
			pcurrent=p1;
			p1=p1->link;
		}
		else
		{
			pcurrent->link=p2;
			pcurrent=p2;
			p2=p2->link;
		}

	}
	if (p1)
	{
		pcurrent->link=p1;
	}
	if (p2)
	{
		pcurrent->link=p2;
	}
	return head;


}



int main()
{
	int a[]={1,4,5,6,7,22,34};
	int b[]={3,4,12,13,15,16};
	node *phead=new node;
	node *phead1=new node;
	phead->data=1;
	phead1->data=3;
	create(&phead,a,7);
	create(&phead1,b,6);
//	printnodelist(phead);
//	cout<<endl;
//	printnodelist_recursion(phead);
	//Reverselist(phead);
	//printlist(phead);
	//cout<<endl;
	node *merge=mubble(phead,phead1);
   	printlist(merge);
	cout<<endl;
	/*printnodelist(phead);*/

	return 0;


}